package jjn.round1;

/**
 * @author Jiang Jining
 * @since 2022-11-13 15:27
 */
public class LeetCode322_CoinChange {
    public int coinChange(int[] coins, int amount) {
        int length = coins.length;
        int[][] dp = new int[length][amount + 1];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i <= amount / coins[0]; ++i) {
            dp[0][i * coins[0]] = i;
        }
        for (int i = 1; i < length; i++) {
            for (int j = 0; j <= amount; j++) {
                int k = j / coins[i];
                for (int l = 0; l <= k; l++) {
                    if (dp[i - 1][j - l * coins[i]] != Integer.MAX_VALUE && dp[i - 1][j - l * coins[i]] + l < dp[i][j]) {
                        dp[i][j] = dp[i - 1][j - l * coins[i]] + l;
                    }
                }
            }
        }
        if (dp[length - 1][amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[length - 1][amount];
    }
}
